package com.jiang.专题.数组.Q42;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/16 18:36
 */
class Solution {
    // 动态规划（前后缀分解）
    // public int trap(int[] height) {
    //     int len = height.length;

    //     int leftMax = 0;
    //     int[] left = new int[len]; // 从左往右能接多少单位雨水
    //     for (int i = 0; i < len; i++) {
    //         if (height[i] >= leftMax) {
    //             leftMax = height[i];
    //         } else {
    //             left[i] = leftMax - height[i];
    //         }
    //     }

    //     int rightMax = 0;
    //     int[] right = new int[len]; // 从右往左能接多少单位雨水
    //     for(int i = len - 1; i >= 0; i--) {
    //         if (height[i] >= rightMax) {
    //             rightMax = height[i];
    //         } else {
    //             right[i] = rightMax - height[i];
    //         }
    //     }

    //     int res = 0;
    //     for (int i = 0; i < len; i++) {
    //         res += Math.min(left[i], right[i]); // 选最小的单位雨水
    //     }
    //     return res;
    // }

    // 递增、递减子序列（前后缀分解）
//    public int trap(int[] height) {
//        int len = height.length;
//        // 找出最高柱子的索引
//        int maxIndex = -1;
//        int maxHeight = 0;
//        for (int i = 0; i < len; i++) {
//            if (height[i] > maxHeight) {
//                maxHeight = height[i];
//                maxIndex = i;
//            }
//        }
//
//        int res = 0;
//        // 从左往右遍历，遍历到maxIndex为止，保证为递增序列
//        int leftMax = 0;
//        for (int i = 0; i < maxIndex; i++) {
//            if (height[i] >= leftMax) {
//                leftMax = height[i];
//            } else {
//                res += leftMax - height[i];
//            }
//        }
//
//        // 从右往左遍历，遍历到maxIndex为止，保证为递减序列
//        int rightMax = 0;
//        for(int i = len - 1; i > maxIndex; i--) {
//            if (height[i] >= rightMax) {
//                rightMax = height[i];
//            } else {
//                res += rightMax - height[i];
//            }
//        }
//
//        return res;
//    }

    // 双指针
    // public int trap(int[] height) {
    //     int res = 0;
    //     int left = 0, right = height.length - 1; // 左右两个指针
    //     int leftMax = 0, rightMax = 0; // 左右两个柱子的最高高度
    //     while (left < right) {
    //         leftMax = Math.max(leftMax, height[left]);
    //         rightMax = Math.max(rightMax, height[right]);
    //         if (leftMax < rightMax) { // 如果左边最高柱子比右边最高柱子矮，则以左边柱子为基准接雨水
    //             res += leftMax - height[left];
    //             left++;
    //         } else { // 如果左边最高柱子比右边最高柱子高，则以右边柱子为基准接雨水
    //             res += rightMax - height[right];
    //             right--;
    //         }
    //     }
    //     return res;
    // }

    // 单调栈
    public int trap(int[] height) {
        int res = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < height.length; i++) {
            while(!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int mid = stack.pop();
                if (stack.isEmpty()) break;
                int left = stack.peek();
                int curWidth = i - left - 1; // 在 最左边的柱子和当前i柱子中， 柱子高度一定是递减的, 宽还包括前面从栈中弹出的柱子
                int curHeight = Math.min(height[left], height[i]) - height[mid];
                res += curHeight * curWidth;
            }
            stack.push(i);
        }
        return res;
    }
}
